package com.zhang.sort;

/**
 * @author ZhangJiXin
 * @Description 基数排序
 * @date 2021/4/25 16:19
 */
public class RadixSort extends Sort<Integer>{
    /**
     * 将数组的基数(个位数，十位数，百位数。。。。)进行排序
     * 先比较个位数进行排序 然后十位数 如果没有十位数 当作0进行比较
     * 排序方法是计数排序 
     * @Author ZhangJiXin
     * @Date 2021/4/27 20:48
     * @return: void
     */
    @Override
    protected void sort() {

        //找到最大数
        Integer max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (max < array[i]){
                max = array[i];
            }
        }
        //循环获取基数 用基数进行排序
        for (int i = 1; i < max; i *= 10) {
            countingSort(i);
        }
    }

    private void countingSort(int index){
        int[] counts = new int[10];
        //计算基数出现的次数
        for (int i = 0; i < array.length; i++) {
            counts[array[i] / index % 10]++;
        }
        //增加前一个元素出现的次数
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

        Integer[] newArray = new Integer[array.length];
        //将元素进行排序 存入新的数组中
        for (int i = array.length - 1; i >= 0; i--) {
            newArray[--counts[array[i] / index % 10]] = array[i];
        }

        //将排序好的元素覆盖到原来的数组
        for (int i = 0; i < newArray.length; i++) {
            array[i] = newArray[i];
        }
    }
}
